"""
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度：O(N^(1-2))
"""


def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):  # 从数组第二位开始
        key = arr[i]  # arr[i] 抽离出来
        j = i - 1
        while j >= 0 and key < arr[j]:  # 如果key小于arr[j]
            arr[j + 1] = arr[j]  # arr[j] 往后挪一位
            j -= 1
        arr[j + 1] = key  # 目标位置赋值


if __name__ == '__main__':
    test_arr = [12, 11, 13, 5, 6]
    insertion_sort(test_arr)
    print(test_arr)
